package com.wtgroup.demo.mianshi.算法.字符串.字符串匹配;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/9 11:25
 */
public class RarbinKarp {

    public static void main(String[] args) {
        System.out.println(match("aaaaaaaaazaaaaaaaaaaaaaaaaa", "zaaaaaaaaaaaaaaaa"));
        "abcdefg".indexOf("def");
    }


    /**
     * hash 值比较
     * 预设: 纯小写英文, 可打印字符
     *
     * 1. 子串求hash (当做进制数字)
     * 2. 滑动动态常数时间更新子串hash值. 一进一出, 如何影响hash值. (公式)
     * @param str 文本串
     * @param pattern 模式串
     * @return
     */
    public static int match(String str, String pattern) {
        if (str.length()<pattern.length()) {
            return -1;
        }

        int R = 26;
        // 防溢出
        long MOD = (long) Math.pow(2, 31);

        // 初始化模式串哈希 和 文本子串哈希
        long h = 0, h_txt = 0;
        for (int i = 0; i < pattern.length(); i++) {
            h = (h * R + char2int(pattern.charAt(i)) ) % MOD;
            h_txt = (h_txt * R + char2int(str.charAt(i))) % MOD;
        }
        if(h==h_txt) return 0;

        // 提前算好 R^L 后面动态更新子串哈希要用 ! 不可用 Math.pow , 因为需要手动处理溢出 !
        long RL = 1;
        for (int i = 0; i < pattern.length(); i++) {
            RL = (RL*R) % MOD;
        }

        for (int i = 1; i < str.length()-pattern.length() + 1; i++) {
            // 更新子串hash
            h_txt = (h_txt * R - char2int(str.charAt(i - 1)) * RL + char2int(str.charAt(i+pattern.length()-1))) % MOD;
            if (h == h_txt) {
                return i;
            }
        }

        return -1;
    }

    // a->0, b->1 ...
    private static int char2int(char c) {
        return c - 'a';
    }

}
